#ifndef _PATH_HOP_H_
#define _PATH_HOP_H_
#include "Interval.h"
#include "Graph.h"
#include "Timer.h"
#include "hlss.h"
using namespace std;
typedef pair<int, int> nid_vol_pair; // <node:volume> pair

class vol_Compare
{
public:
    bool operator()(const nid_vol_pair p1, const nid_vol_pair p2) const
    {
		return p1.second >= p2.second;
    }    
};

class Path_Hop
{
public:
    map<int, set<nid_vol_pair, vol_Compare> > descendants_sort_list;    
    map<int, set<int> > ancestors_list,  descendants_list;
    map<int, set<int> > Lin, Lout;
    vector<vector<int> > Lin_vec, Lout_vec;
    size_t top_nid, bottom_nid;
    Interval *p_interval_t; //tree interval labeling instance
    Interval *p_interval_nt; //non-tree interval labeling instance; (non overlapping)
    int **tree_interval; // tree interval, 2D array
    Interval *p_intl;// for correctness test 
    Graph& gra, tc; // hold the graph data
    vector<Vertex> topo; // topologically sorted vertices
    int node_count; // the number of vertices
    //for query processing, Lin Lout intervals
    //set<int> ancestors_Lin, descendants_Lout;
    vector<int> ancestors_Lin_vec, descendants_Lout_vec;
    bool **utc;
    set<int> anc_set, desc_set;
    int *dfs_array;
    int hop_cnt;
    int tc_cnt_original, tc_cnt;
    float q_time;
    int parent_jump;
    //multimap<int, int> edges, edges_max, edges_final;
    // bipartite graph's vertices, exluding the center node; 1st col = nid, 2nd col = edge cnt
    map<int, set<int> > adj_nodes_max, adj_nodes_final, adj_nodes, adj_nodes_revert;
    float all_density;
	hlss *hl;
public:
    Path_Hop(Graph& g); //construction func;
    ~Path_Hop(); // desctruction func;
    void reduce_graph(Graph& g); // transitive reduction;
    void init_tree_interval(); //copy intervals from p_interval_t to tree_interval
    void init_dfs_array(); // construct a array in BFS order,sorted by "begin" value,  for get_descendants() function;
    void topo_sort(); // topological sort;
    bool is_descendant(Vertex u, Vertex v); // Test if v is a TREE descendant of u; i.e. only via tree edges;
    bool is_descendant(size_t top_nid, size_t bottom_nid); // test if bottom_nid is a TREE descendant of top_nid; i.e. only via tree edges; overloaded function;
    int interval_2_nid(int begin, int end); // get node's id from it's tree interval label;
    int begin_2_nid(int begin);//get node is from it's tree interval's "begin" value
    void construct_descendants_list(); 
    void construct_descendants_sort_list();
    int calc_in_vol(size_t nid); // calculate in volume, using UTC matrix;
    int calc_out_vol(size_t nid); // calculate out volume, using UTC matrix;
    float calc_den(size_t top_nid, size_t bottom_nid, int& in_out);// calc density of a path hop which is uniquely specified by a pair of a top node and a bottom node; using utc
    int has_non_tree_edge(Vertex v); // test if a node has any non-tree edges;
    int has_non_tree_edge(int nid); // test if a node has any non-tree edges;    
    bool has_interval(Vertex u, Vertex v);  // test if u's non-tree intervals has v's tree-interval  (exactly equals);
    float select_densest_hop(); // currently in use; using utc
    int get_first_of_desc_sort_list(int v); // get the descendant with "largest out-volume"; (lazy re-evaluation);
    void add_to_Lin(int v); // add v to the Lin of concerned nodes; using utc
    void add_to_Lout(int v); // add v to the Lout of concerned nodes; using utc
    void add_to_Lin_Lout_sub(int top_nid, int bottom_nid); // add top_nid and bottom_nid to the Lin Lout; for densest sub graph
    void update_utc(int top_nid, int bottom_nid, int in_out); // update the utc matrix;
    void update_utc_sub(int top_nid, int bottom_nid); // update the utc, if a densest sub graph is select;
    void print_path_hop_labels(int node_count); // print generated path-hop labels;
    int path_hop_index_size(); // return index size;
    void post_process(); // copy Lin and Lout;
    bool reach(int nid1, int nid2); // test if nid1 reaches nid2; 
    bool bfs_reach(int nid1, int nid2); // test if nid1 reaches nid2, using naive Breadth-First-Search
    void user_query(); // prompt for user input and do query;
    int check_correctness(int test_size); // compare results with multi-interval labeling;
    //int check_correctness2(int test_size); // compare results with multi-interval labeling for 3hop
    void batch_query(int query_size); // do a batch of queries to test query processing efficiency;
    void batch_query_bfs(int query_size); // do a batch of queries to test query processing efficiency, use BFS
    void set_2_vector();
    void init_utc(); //init the uncovered tc matrix, 0 = unreachable, 1 = reaachbale but not covered yet , 2 = reachable and covered;
    int num_special_nodes();
    void remove_redundant_Lin_Lout_in_vertex(); // check the Lin of each vertex to ensure there is no A-D relationship among the Lin nodes set
    void remove_redundant_Lin_Lout_in_tree(); // remove the Lin/Lout redundancies on a tree level.
    float densest_sub_graph(int top_nid, int bottom_nid); // select the densest sub bipartite graph;
    void init_parent_pointer();
    int single_edge_connection();
	void create_label();
	int hlss_on_utc();
};
#endif




